package com.rgbgame.game;

import processing.core.PApplet;

import java.util.ArrayList;
import java.util.Hashtable;

    final class SpatialPartition {
        final float edgeTolerance = 5.0f; // add 5 pixels to each bin to catch
        // edge cases
        Box2d bufferBox = new Box2d(0, 0, 0, 0);
        Hashtable hashBuffer = new Hashtable();

        private float resolution; // size of cell in one direction
        public float minX;
        public float maxX;
        public float minY;
        public float maxY;
        private int xCells;
        private int yCells;
        private ArrayList[] collidingWalls; // each element is an arraylist of
        // walls that are in range
        // private com.rgbgame.game.SolidWall2d[][] collidingWalls; //change to array
        // representation eventually, since ArrayList has a lot of overhead

        private ArrayList[] staticCollidingStruts; // Store non-moving
        // colliding struts
        // separately for efficiency
        private ArrayList[] dynamicCollidingStruts;
        private Strut[] dcStrutList;

        private int indexNumber(int i, int j) {
            int ind = xCells * j + i;
            if (ind < 0) {
                return 0;
            } else if (ind < xCells * yCells) {
                return ind;
            } else {
                return xCells * yCells - 1;
            }
            // This won't return a bad value, instead it just collapses
            // everything outside valid ranges to the first or last grid points
        }

        private int iIndex(int num) {// test this!!!
            return (num % xCells);
        }

        private int jIndex(int num) {// test this!!!
            return ((num - iIndex(num)) / xCells);
        }

        private int getCell(Vector3d vec) {
            int myI = (int) Math.floor((vec.x - minX) / resolution);
            int myJ = (int) Math.floor((vec.y - minY) / resolution);
            if (myI < 0) {
                myI = 0;
            }
            if (myI > xCells - 1) {
                myI = xCells - 1;
            }
            if (myJ < 0) {
                myJ = 0;
            }
            if (myJ > yCells - 1) {
                myJ = yCells - 1;
            }
            return indexNumber(myI, myJ);
        }

        private Box2d getRange(int iStart, int iEnd, int jStart, int jEnd) {
            // debugCounter++;
            float startX = minX + iStart * resolution; // from left edge of
            // start box
            float endX = minX + (iEnd + 1) * resolution; // to right edge of
            // end box
            float startY = minY + jStart * resolution;
            float endY = minY + (jEnd + 1) * resolution;
            return new Box2d(new Vector3d(startX, startY, 0), new Vector3d(
                    endX, endY, 0));
        }

        public SpatialPartition(float res, ArrayList myWalls,
                                ArrayList staticStruts, ArrayList dynamicStruts) {
            resolution = res;
            // Find min and max wall values in x and y coords
            minX = 0;
            maxX = 0;
            minY = 0;
            maxY = 0;
            // Set mins/maxes to first element or zero, depending on whether
            // first element exists
            if (myWalls.size() > 0) {
                minX = ((SolidWall2d) myWalls.get(0)).wallA.x;
                maxX = minX;
                minY = ((SolidWall2d) myWalls.get(0)).wallA.y;
                maxY = minY;
            }
            // First add walls
            for (int i = 0; i < myWalls.size(); i++) {
                SolidWall2d myWall = (SolidWall2d) myWalls.get(i);
                if (myWall.wallA.x < minX) {
                    minX = myWall.wallA.x;
                }
                if (myWall.wallB.x < minX) {
                    minX = myWall.wallB.x;
                }
                if (myWall.wallA.x > maxX) {
                    maxX = myWall.wallA.x;
                }
                if (myWall.wallB.x > maxX) {
                    maxX = myWall.wallB.x;
                }
                if (myWall.wallA.y < minY) {
                    minY = myWall.wallA.y;
                }
                if (myWall.wallB.y < minY) {
                    minY = myWall.wallB.y;
                }
                if (myWall.wallA.y > maxY) {
                    maxY = myWall.wallA.y;
                }
                if (myWall.wallB.y > maxY) {
                    maxY = myWall.wallB.y;
                }
            }
            // Now add static struts
            for (int i = 0; i < staticStruts.size(); i++) {
                Strut myStrut = (Strut) staticStruts.get(i);
                if (myStrut.pA.position.x < minX) {
                    minX = myStrut.pA.position.x;
                }
                if (myStrut.pB.position.x < minX) {
                    minX = myStrut.pB.position.x;
                }
                if (myStrut.pA.position.x > maxX) {
                    maxX = myStrut.pA.position.x;
                }
                if (myStrut.pB.position.x > maxX) {
                    maxX = myStrut.pB.position.x;
                }
                if (myStrut.pA.position.y < minY) {
                    minY = myStrut.pA.position.y;
                }
                if (myStrut.pB.position.y < minY) {
                    minY = myStrut.pB.position.y;
                }
                if (myStrut.pA.position.y > maxY) {
                    maxY = myStrut.pA.position.y;
                }
                if (myStrut.pB.position.y > maxY) {
                    maxY = myStrut.pB.position.y;
                }
            }
            minX -= resolution;
            maxX += resolution;
            minY -= resolution;
            maxY += resolution; // add an extra bin so that we don't land
            // exactly on the edges with our outer walls -
            // can lead to issues

            // Now find the appropriate numbers of cells, given the resolution
            // and range - use ceil to err on the side of caution and add an
            // extra cell if needed
            xCells = (int) Math.ceil((maxX - minX) / resolution);
            yCells = (int) Math.ceil((maxY - minY) / resolution);

            // Next we add the walls to the grid. We use a slow but simple
            // process to do this, as it should only happen upon map parsing,
            // not during simulation.
            // Note: this is really slow for large numbers of walls...
            // First allocate the array of ArrayLists to be xCells*yCells large.
            // Note: the (i,j) cell is going to be at index (xCells*j + i), as
            // 1-d arrays tend to be a bit easier to use - use indexNumber(i,j)
            // toget this, just to be safe
            collidingWalls = new ArrayList[xCells * yCells];
            for (int i = 0; i < collidingWalls.length; i++) {
                collidingWalls[i] = new ArrayList(); // allocate
                Box2d currentRange = getRange(iIndex(i), iIndex(i), jIndex(i),
                        jIndex(i));
                currentRange.expand(edgeTolerance);
                for (int j = 0; j < myWalls.size(); j++) {
                    // if wall pierces range, add it on to collidingWalls[i]
                    SolidWall2d myWall = (SolidWall2d) myWalls.get(j);
                    if (currentRange.hitBy(myWall.wallA, myWall.wallB)) {
                        collidingWalls[i].add(myWall);
                    }
                }
            }

            staticCollidingStruts = new ArrayList[xCells * yCells];
            for (int i = 0; i < staticCollidingStruts.length; i++) {
                staticCollidingStruts[i] = new ArrayList(); // allocate
                Box2d currentRange = getRange(iIndex(i), iIndex(i), jIndex(i),
                        jIndex(i));
                currentRange.expand(edgeTolerance);
                for (int j = 0; j < staticStruts.size(); j++) {
                    // if wall pierces range, add it on to collidingWalls[i]
                    Strut myStrut = (Strut) staticStruts.get(j);
                    if (currentRange.hitBy(myStrut.pA.position,
                            myStrut.pB.position)) {
                        staticCollidingStruts[i].add(myStrut);
                    }
                }
            }

            dcStrutList = new Strut[dynamicStruts.size()];
            for (int i = 0; i < dcStrutList.length; i++) {
                dcStrutList[i] = (Strut) dynamicStruts.get(i);
            }
            dynamicCollidingStruts = new ArrayList[xCells * yCells];
            for (int i = 0; i < dynamicCollidingStruts.length; i++) {
                dynamicCollidingStruts[i] = new ArrayList(); // allocate
                Box2d currentRange = getRange(iIndex(i), iIndex(i), jIndex(i),
                        jIndex(i));
                currentRange.expand(edgeTolerance);
                for (int j = 0; j < dynamicStruts.size(); j++) {
                    // if strut pierces range, add it on to list
                    Strut myStrut = (Strut) dynamicStruts.get(j);
                    if (currentRange.hitBy(myStrut.pA.position,
                            myStrut.pB.position)) {
                        dynamicCollidingStruts[i].add(myStrut);
                    }
                }
            }
        }

        public void refreshDynamicPartitioning() {
            // This is not as slow as the initial method, but it's definitely
            // not optimal
            Strut buffer;
            for (int i = 0; i < dcStrutList.length; i++) {
                buffer = dcStrutList[i];
                // Check initial start/end cells
                float oldMinX = PApplet.min(buffer.pA.truePositionLast.x,
                        buffer.pB.truePositionLast.x);
                float oldMaxX = PApplet.max(buffer.pA.truePositionLast.x,
                        buffer.pB.truePositionLast.x);
                float oldMinY = PApplet.min(buffer.pA.truePositionLast.y,
                        buffer.pB.truePositionLast.y);
                float oldMaxY = PApplet.max(buffer.pA.truePositionLast.y,
                        buffer.pB.truePositionLast.y);
                float newMinX = PApplet.min(buffer.pA.position.x, buffer.pB.position.x);
                float newMaxX = PApplet.max(buffer.pA.position.x, buffer.pB.position.x);
                float newMinY = PApplet.min(buffer.pA.position.y, buffer.pB.position.y);
                float newMaxY = PApplet.max(buffer.pA.position.y, buffer.pB.position.y);
                int oldMinI = (int) Math.floor((oldMinX - minX) / resolution);
                int oldMinJ = (int) Math.floor((oldMinY - minY) / resolution);
                int oldMaxI = (int) Math.floor((oldMaxX - minX) / resolution);
                int oldMaxJ = (int) Math.floor((oldMaxY - minY) / resolution);
                int newMinI = (int) Math.floor((newMinX - minX) / resolution);
                int newMinJ = (int) Math.floor((newMinY - minY) / resolution);
                int newMaxI = (int) Math.floor((newMaxX - minX) / resolution);
                int newMaxJ = (int) Math.floor((newMaxY - minY) / resolution);
                oldMinI = constrainInt(oldMinI, 0, xCells - 1);
                oldMinJ = constrainInt(oldMinJ, 0, yCells - 1);
                oldMaxI = constrainInt(oldMaxI, 0, xCells - 1);
                oldMaxJ = constrainInt(oldMaxJ, 0, yCells - 1);
                newMinI = constrainInt(newMinI, 0, xCells - 1);
                newMinJ = constrainInt(newMinJ, 0, yCells - 1);
                newMaxI = constrainInt(newMaxI, 0, xCells - 1);
                newMaxJ = constrainInt(newMaxJ, 0, yCells - 1);

                for (int ai = minInt(oldMinI, newMinI); ai < maxInt(oldMaxI,
                        newMaxI) + 1; ai++) {
                    for (int aj = minInt(oldMinJ, newMinJ); aj < maxInt(
                            oldMaxJ, newMaxJ) + 1; aj++) {
                        // Remove from arraylist unless it's also in the new one
                        int indexNum = dynamicCollidingStruts[indexNumber(ai,
                                aj)].indexOf(buffer);
                        if (ai <= newMaxI && ai >= newMinI && aj <= newMaxJ
                                && aj >= newMinJ) {
                            // If indexNum == -1, then the strut is not already
                            // in our list, so we add it
                            if (indexNum == -1)
                                dynamicCollidingStruts[indexNumber(ai, aj)]
                                        .add(buffer);
                        } else {
                            // If we're outside of the new range of indices,
                            // then if the strut is in the old list we remove
                            // it.
                            // This check also means that we can take the first
                            // step with the more accurate method (which we've
                            // really only done so that it's consistent with the
                            // other stuff)
                            if (indexNum != -1)
                                dynamicCollidingStruts[indexNumber(ai, aj)]
                                        .remove(indexNum);
                        }
                    }
                }
            }
        }

        private int minInt(int i1, int i2) {
            if (i1 > i2)
                return i2;
            else
                return i1;
        }

        private int maxInt(int i1, int i2) {
            if (i2 > i1)
                return i2;
            else
                return i1;
        }

        private int constrainInt(int in, int inmin, int inmax) {
            if (in < inmin)
                return inmin;
            if (in > inmax)
                return inmax;
            return in;
        }

        public SolidStrut[] getSolidStrutsInRange(Box2d _range) {
            Hashtable hashResult = hashBuffer;
            hashBuffer.clear();
            int beginCellIndex = getCell(_range.minVec);
            int endCellIndex = getCell(_range.maxVec);
            int iBegin = iIndex(beginCellIndex);
            int jBegin = jIndex(beginCellIndex);
            int iEnd = iIndex(endCellIndex);
            int jEnd = jIndex(endCellIndex);
            for (int i = iBegin; i < iEnd + 1; i++) {
                for (int j = jBegin; j < jEnd + 1; j++) {
                    int currIndex = indexNumber(i, j);
                    for (int k = 0; k < staticCollidingStruts[currIndex].size(); k++) {
                        Strut currStrut = (Strut) staticCollidingStruts[currIndex].get(k);
                        SolidStrut s;
                        if (currStrut.colliding) {
                            s = (SolidStrut) currStrut;
                            hashResult.put(s, s);
                        }
                    }
                    for (int k = 0; k < dynamicCollidingStruts[currIndex].size(); k++) {
                        Strut currStrut = (Strut) dynamicCollidingStruts[currIndex].get(k);
                        SolidStrut s;
                        if (currStrut.colliding) {
                            s = (SolidStrut) currStrut;
                            hashResult.put(s, s);
                        }
                    }
                }
            }
            Object[] oresult = (hashResult.values().toArray());
            SolidStrut[] result = new SolidStrut[oresult.length];
            for (int i = 0; i < oresult.length; i++) {
                result[i] = (SolidStrut) oresult[i];
            }
            return result;
        }

        public Strut[] getStrutsInRange(Box2d _range) {
            // debugCounter++;
            Hashtable hashResult = hashBuffer; // use a hashtable so we don't
            // have dupes - though we do pay
            // an efficiency penalty
            hashBuffer.clear();
            int beginCellIndex = getCell(_range.minVec);
            int endCellIndex = getCell(_range.maxVec);
            int iBegin = iIndex(beginCellIndex);
            int jBegin = jIndex(beginCellIndex);
            int iEnd = iIndex(endCellIndex);
            int jEnd = jIndex(endCellIndex);
            for (int i = iBegin; i < iEnd + 1; i++) {
                for (int j = jBegin; j < jEnd + 1; j++) {
                    int currIndex = indexNumber(i, j);
                    for (int k = 0; k < staticCollidingStruts[currIndex].size(); k++) {
                        Strut currStrut = (Strut) staticCollidingStruts[currIndex]
                                .get(k);
                        hashResult.put(currStrut, currStrut);
                    }
                    for (int k = 0; k < dynamicCollidingStruts[currIndex]
                            .size(); k++) {
                        Strut currStrut = (Strut) dynamicCollidingStruts[currIndex]
                                .get(k);
                        hashResult.put(currStrut, currStrut);
                    }
                }
            }
            Object[] oresult = (hashResult.values().toArray());
            Strut[] result = new Strut[oresult.length];
            for (int i = 0; i < oresult.length; i++) {
                result[i] = (Strut) oresult[i];
            }

            // here we sort the struts so the ordering is deterministic
            // OPT: bubble sort? you've got to be kidding me... same with
            // getWalls... function
            /*
               boolean isSorted = false;
               com.rgbgame.game.Strut swap;
               if (result.length > 1) {
                   while (!isSorted) {
                       isSorted = true;
                       for (int i = 0; i < result.length - 1; i++) {
                           if (result[i].id > result[i + 1].id) {
                               // swap i and i+1
                               swap = result[i];
                               result[i] = result[i + 1];
                               result[i + 1] = swap;
                               isSorted = false;
                           }
                       }
                   }
               }*/

            return result;
        }

        public Strut[] getStrutsInRange(float x1, float y1, float x2, float y2) {
            // debugCounter++;
            bufferBox.set(x1, y1, x2, y2);
            return getStrutsInRange(bufferBox);
        }

        public Strut[] getSolidStrutsInRange(float x1, float y1, float x2, float y2) {
            // debugCounter++;
            bufferBox.set(x1, y1, x2, y2);
            return getSolidStrutsInRange(bufferBox);
        }

        public SolidWall2d[] getWallsInRange(Box2d _range) {
            // debugCounter++;
            Hashtable hashResult = hashBuffer; // use a hashtable so we don't
            // have dupes
            hashBuffer.clear();
            int beginCellIndex = getCell(_range.minVec);
            int endCellIndex = getCell(_range.maxVec);
            int iBegin = iIndex(beginCellIndex);
            int jBegin = jIndex(beginCellIndex);
            int iEnd = iIndex(endCellIndex);
            int jEnd = jIndex(endCellIndex);
            for (int i = iBegin; i < iEnd + 1; i++) {
                for (int j = jBegin; j < jEnd + 1; j++) {
                    int currIndex = indexNumber(i, j);
                    for (int k = 0; k < collidingWalls[currIndex].size(); k++) {
                        SolidWall2d currWall = (SolidWall2d) collidingWalls[currIndex]
                                .get(k);
                        hashResult.put(currWall, currWall);// "wall_"+currWall.idNum,currWall);
                    }
                }
            }
            Object[] oresult = (hashResult.values().toArray());
            SolidWall2d[] result = new SolidWall2d[oresult.length];
            for (int i = 0; i < oresult.length; i++) {
                result[i] = (SolidWall2d) oresult[i];
/*

                if (debugFlag) {
                    pushMatrix();
                    translate(cameraX, cameraY);
                    result[i].draw(Color.red, game.this);
                    result[i].skipNextDraw();
                    popMatrix();
                }
*/

                
            }
/*
			// here we sort the walls so the ordering is deterministic
			boolean isSorted = false;
			com.rgbgame.game.SolidWall2d swap;
			if (result.length > 1) {
				while (!isSorted) {
					isSorted = true;
					for (int i = 0; i < result.length - 1; i++) {
						if (result[i].idNum > result[i + 1].idNum) {
							// swap i and i+1
							swap = result[i];
							result[i] = result[i + 1];
							result[i + 1] = swap;
							isSorted = false;
						}
					}
				}
			}*/

            return result;
        }

        public SolidWall2d[] getWallsInRange(float x1, float y1, float x2,
                                             float y2) {
            // debugCounter++;
            bufferBox.set(x1, y1, x2, y2);
            return getWallsInRange(bufferBox);
        }

        public void draw() {
            int initI = iIndex(getCell(new Vector3d(-rgbGame.game.cameraX, -rgbGame.game.cameraY, 0)));
            int initJ = jIndex(getCell(new Vector3d(-rgbGame.game.cameraX, -rgbGame.game.cameraY, 0)));
            int endI = iIndex(getCell(new Vector3d(-rgbGame.game.cameraX + rgbGame.width, -rgbGame.game.cameraY
                    + rgbGame.height, 0)));
            int endJ = jIndex(getCell(new Vector3d(-rgbGame.game.cameraX + rgbGame.width, -rgbGame.game.cameraY
                    + rgbGame.height, 0)));
            //com.rgbgame.game.Box2d test = getRange(initI, initI, initJ, initJ);
            //com.rgbgame.game.Box2d test2 = getRange(initI + 1, initI + 1, initJ + 1, initJ + 1);
            for (int i = initI; i < endI + 1; i++) {
                for (int j = initJ; j < endJ + 1; j++) {
                    Box2d myBox = getRange(i, i, j, j);
                    int currIndex = indexNumber(i, j);
                    if (dynamicCollidingStruts[currIndex].size() > 0) {
                        // collidingWalls[currIndex].size() +
                        // staticCollidingStruts[currIndex].size() +
                        // dynamicCollidingStruts[currIndex].size() > 0 ){
                        rgbGame.pApplet.fill(255, 255, 255, 100);
                    }
                    myBox.draw();
                    rgbGame.pApplet.noFill();
                }
            }
        }

    }
